import java.util.*;

public class Test {
    public static void moveZeros(int[]arr){
        for (int cur = 0,dest=-1; cur < arr.length; cur++) {
            if(arr[cur]!=0){
                swap(arr,++dest,cur);
            }
        }
    }
    public static void swap(int[]arr,int e1,int e2){
        int tmp=arr[e1];
        arr[e1]=arr[e2];
        arr[e2]=tmp;
    }
    public static void duplicateZeros(int[] arr) {
  /*      int j=-1,i=0;//j是最后一个复写的元素
        int n=arr.length;
        while(i<n){
            if(arr[i]==0){
                j+=2;
            }else{
                j++;
            }
            if(j>=n-1){//j走到末尾了
                break;
            }
            i++;
        }
        //System.out.println(arr[i-1]);
        //2.从后往前复写
        if(j==n){
            arr[n-1]=0;
            j-=2;
            i--;
        }
        for(int cur=i,dest= j;cur>=0;cur--,dest--){
            if(arr[cur]!=0){
                arr[dest]=arr[cur];
            }
            else{
                arr[dest]=arr[cur];
                arr[--dest]=arr[cur];
            }
        }*/
        //找到最后一个复写的元素
        int dest=-1,cur=0,n=arr.length;//[cur,n-1]是待检测区域
        for(dest=-1,cur=0;cur<n;cur++) {
            if (arr[cur] == 0) {
                dest += 2;
            } else {
                dest++;
            }
            if (dest >= n - 1) break;//等下判断dest的位置
        }
            if(dest==n){
                arr[n-1]=0;
                dest-=2;
                cur--;
            }
            for(;cur>=0;cur--){
                if(arr[cur]==0){
                    arr[dest--]=arr[cur];
                    arr[dest--]=arr[cur];
                }else{
                    arr[dest--]=arr[cur];
                }
            }

    }
    public int maxArea(int[] height){
        int left=0,right=height.length-1;
        PriorityQueue<Integer>maxHeap=new PriorityQueue<>(((o1, o2) -> o2-o1));
        while(left<right){
            int shortHeight=Math.min(height[left],height[right]);
            int weight=right-left;
            int volume=weight*shortHeight;
            if(height[left]==shortHeight){
                left++;
            }else{
                right--;
            }
            maxHeap.add(volume);

        }
        return maxHeap.peek();
    }
    public int triangleNumber(Integer[] nums){
        Arrays.sort(nums, new Comparator<Integer>(){

            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        int n=nums.length;
        int ret=0;
        for (int i = n-1; i >= 2;i--) {
            for(int j=0,k=i-1;j<k;){
                if(nums[j]+nums[k]>nums[i]){
                    ret+=k-j;
                    k--;
                }else{
                    j++;
                }
            }
        }
        return ret;
    }
    public int[] twoSum(int[]arr,int target){
        int left=0,right=arr.length-1;
        while(left<right){
            if(arr[left]+arr[right]>target){
                right--;
            } else if (arr[left]+arr[right]<target) {
                left++;
            }else{
                return new int[]{arr[left],arr[right]};
            }
        }
        return new int[]{0};

    }
    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>>ret=new ArrayList<>();
        Arrays.sort(nums);
        for (int cur = 0; cur < nums.length; cur++) {
            if(nums[cur]>0) break;
            int target=-nums[cur];
            int left=cur+1,right=nums.length-1;
            while(left<right){

                if(nums[left]+nums[right]>target) right--;
                else if (nums[left]+nums[right]<target) left++;
                else {
                   ret.add(new ArrayList<Integer>(Arrays.asList(nums[cur],nums[left],nums[right])));

                    while (left<right&&nums[left]==nums[left+1]){
                        left++;
                    }
                    while (left<right&&nums[right]==nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }
            }
            while (cur+1<nums.length&&nums[cur]==nums[cur+1]){
                cur++;
            }

        }
        return ret;
    }
    public List<List<Integer>> fourSum(int[] nums, int target){
        List<List<Integer>>ret=new ArrayList<>();
        Arrays.sort(nums);
        int n=nums.length;
        for (int i = 0; i < n; i++ ) {
            int a=nums[i];
            for(int j=i+1;j<n;j++){
                int b=nums[j];
                int left=j+1,right=n-1;
                while(left<right){
                    if(nums[left]+nums[right]<target-a-b) left++;
                    else if(nums[left]+nums[right]>target-a-b) right--;
                    else{
                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[j],nums[left],nums[right])));
                        while(left<right&&nums[left]==nums[left+1]) left++;
                        while(left<right&&nums[right]==nums[right-1]) right--;
                        left++;right--;
                    }
                }
                while (j<n-1&&nums[j]==nums[j+1]){
                    j++;
                }
            }
            while (i<n-1&&nums[i]==nums[i+1]){
                i++;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Test test=new Test();
        int[]nums={1000000000,1000000000,1000000000,1000000000};
        System.out.println(test.fourSum(nums, -294967296));

    }

    public static void main5(String[] args) {
        int[]arr={-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0};
        Test test=new Test();
        System.out.println(test.threeSum(arr));
    }

    public static void main4(String[] args) {
        int[]arr={2,7,11,15};
        Test test=new Test();
        int[]ret=test.twoSum(arr,9);
        for(int x:ret){
            System.out.print(x+" ");
        }
        //System.out.println(test.triangleNumber(arr));
    }

    public static void main3(String[] args) {
        int[]arr={1,8,6,2,5,4,8,3,7};
        Test test=new Test();
        System.out.println(test.maxArea(arr));
    }
    public static void main2(String[] args) {
        int arr[] = {1,0,2,3,0,4,5,0};
        duplicateZeros(arr);
        for (int x : arr) {
            System.out.print(x+" ");
        }
    }
    public static void main1(String[] args) {
        int arr[]={0,1,2,7};
        moveZeros(arr);
        for(int x:arr){
            System.out.print(x+" ");
        }
    }


}
